package com.njupt.Tree;

import java.util.ArrayList;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/12/9 16:27
 * @Description: 669. 修剪二叉搜索树
 * @Version: 1.0
 */


public class TrimBST {

    public TreeNode trimBST1(TreeNode root, int low, int high) {
        //1、中序遍历，将遍历的结果保存在ArrayList中
        //2、遍历ArrayList,对于ArrayList中的每一个值如果小于low || 大于high，那么就删除节点

        ArrayList<Integer> results = new ArrayList<>();
        traverse(root,results);
        for (int i = 0; i < results.size(); i++) {
            if(results.get(i) < low || results.get(i) > high){
                root = deleteNode(root,results.get(i));
            }
        }
        return root;
    }

    private TreeNode deleteNode(TreeNode root, int val) {
        if(root == null) return null;

        if(root.val == val){
            if(root.left == null){
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }else {
                TreeNode cur = root.right;
                while(cur.left != null){
                    cur = cur.left;
                }
                cur.left = root.left;
                root = root.right;
                return root;
            }
        }

        if(val < root.val){
            root.left = deleteNode(root.left,val);
        }
        if(val > root.val){
            root.right = deleteNode(root.right,val);
        }
        return root;
    }

    private void traverse(TreeNode root, ArrayList<Integer> results) {
        if(root == null) return;

        traverse(root.left,results);
        results.add(root.val);
        traverse(root.right,results);
    }


    public TreeNode trimBST(TreeNode root, int low, int high) {

        if(root == null){
            return null;
        }
        if(root.val < low){
            TreeNode rightNode = trimBST(root.right, low, high);
            return rightNode;
        }
        if(root.val > high){
            TreeNode leftNode = trimBST(root.left, low, high);
            return leftNode;
        }
        root.left = trimBST(root.left,low,high);
        root.right = trimBST(root.right,low,high);
        return root;
    }

    public static void main(String[] args) {
//        TreeNode root = new TreeNode(1);
//        root.left = new TreeNode(0);
//        root.right = new TreeNode(2);


        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(0);
        root.right = new TreeNode(4);
        root.left.right = new TreeNode(2);
        root.left.right.left = new TreeNode(1);

        TrimBST test = new TrimBST();
        TreeNode root1 = test.trimBST(root, 1, 3);

        System.out.println();
    }
}
